package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;

/**
 * 从表尾开始寻找模节点，即：从链表表尾开始找到第一个满足 i%k==0 的节点
 * @author zifangsky
 *
 */
public class Problem_016_FindModeNodeFromEnd {
	
	/**
	 * 思路：
	 * 		headNode首先移动k个节点，然后headNode和result再分别逐步向表尾移动，
	 * 当headNode移动到NULL时，此时result即为目标节点
	 * @时间复杂度 O(n)
	 * @param headNode
	 * @param k
	 * @return
	 */
	public SinglyNode getModularNode(SinglyNode headNode,int k){
		SinglyNode result = headNode;
		if(k <= 0){
			return null;
		}
		
		for(int i=1;i<=k;i++){
			if(headNode != null){
				headNode = headNode.getNext();
			}else{
				return null;
			}
		}
		
		while (headNode != null) {
			result = result.getNext();
			headNode = headNode.getNext();
		}

		return result;
	}

	@Test
	public void testMethods(){
		SinglyNode headNode = new SinglyNode(1);
		
		SinglyNode currentNode = headNode;
		for(int i=2;i<=7;i++){
			SinglyNode tmpNode = new SinglyNode(i);
			currentNode.setNext(tmpNode);
			currentNode = tmpNode;
		}
		
		//遍历初始链接
		SinglyNodeOperations.print(headNode);
		
		System.out.println("目标节点是： " + getModularNode(headNode,3));
	}
	
}
